package ACwing.P3SearchandGraph.TopologicalSorting;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Date : 2023-04-02
 * @Description:848. 有向图的拓扑序列
 * 有向图  没有环的图 才有拓扑序列
 * 对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
 * 入度为0的点 都可以当成起点
 * while queue  所有入度为0的点  ，
 * 求出t的所有出边t->k
 * 删掉t->k  d[j]--
 * if d[k]==0
 * queue<-k
 *
 */
public class DirectedGraphs {
    static int N=100010;
    static  int n,m;
    //领接表的存储方式 头节点h 存储的值e，当前用到的下标idx
    static  int []h=new int[N],e=new int[N],ne=new int [N];
    static  int idx;
    //q是队列，  d是每个点的入度
    static  int [] q=new int[N],d=new int[N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        //批量赋值 不可达
        Arrays.fill(h,-1);
        for (int i = 0; i < m; i++) {
            int a,b;
            a = scanner.nextInt();
            b = scanner.nextInt();
            add(a,b);
        }

        }
        //把边加入图
        static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}
